package com.gwcloud.leetcode.tags.backtrace;

import java.util.ArrayList;
import java.util.List;

/** 
* @ClassName   : Leetcode126 
* @author      : ganwei 
* @date        : 2020年5月9日 
* @Description : 126. 单词接龙 II 
*/
public class Leetcode0126 {
	
	List<List<String>> result = new ArrayList<>();
	List<List<String>> shortpath = new ArrayList<>();
	List<String> path = new ArrayList<>();
	Integer pathDis = Integer.MAX_VALUE;
	boolean[] isVisited;
    
	/**
     * -解题思路，回溯回溯！！
     */
	public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
		if(!wordList.contains(endWord)) {
			return result;
		}
		
		isVisited = new boolean[wordList.size()];
		path.add(beginWord);
		backtrack(beginWord, endWord, wordList,path);
		
    	return result;
    }
	
	/**
	 * -回溯主体
	 */
	public void backtrack(String beginWord, String endWord, List<String> wordList, List<String> path) {

		if(path.size() > pathDis) {
			return;
		}
		
		if(endWord.equals(path.get(path.size()-1))){
			//path.add(endWord);
			
			if(path.size() < pathDis) {
				result.clear();
				pathDis = path.size();
				result.add(new ArrayList<String>(path));
				
			}else if(path.size() == pathDis) {
				result.add(new ArrayList<String>(path));
			}
			return;
		}
		if(path.size() == wordList.size()) {
			return;
		}
		
		for(int i = 0; i < wordList.size(); i++) {
			if(isVisited[i]) {
				continue;
			}
			
			if(isConnect(wordList.get(i), path.get(path.size()-1))) {
				path.add(wordList.get(i));
				isVisited[i] = true;
				backtrack(beginWord, endWord, wordList, path);
				path.remove(path.size()-1);
				isVisited[i] = false;
			}
			
		}
		
	}
	/**
	 * -判断两个字符串
	 */
	public boolean isConnect(String s1, String s2) {
		if(s1.length() != s2.length()) {
			return false;
		}
		
		int count = 0;
		for(int i = 0; i < s1.length(); i++) {
			if(s1.charAt(i) != s2.charAt(i)) {
				count++;
			}
		}
		
		if(count == 1) {
			return true;
		}else {
			return false;
		}
	}
	
	public static void main(String[] args) {
		Leetcode0126 l126 = new Leetcode0126();
		List<String> wordList = new ArrayList<String>();
		wordList.add("hot");
		wordList.add("dot");
		wordList.add("dog");
		wordList.add("lot");
		wordList.add("log");
		wordList.add("cog");
		
		
		
		
		l126.findLadders("hit", "cog", wordList);
		System.out.println("--------------------------");
		for(List<String> l : l126.result) {
			for(String s : l) {
				System.out.print(s);
				System.out.print("-");
			}
			System.out.println();
		}
		System.out.println("--------------------------");
	}
}
